/**
 * 
 */
package hihocoder;

/**
 * @author zhongfang
 *
 */
public class NumberofLongestIncreasingSubsequence {
	public int findLengthOfLCIS(int[] nums) {
		int count = 0;
		int max = 0;
		for (int i = 0; i < nums.length; i++) {
			if (i == 0 || nums[i] <= nums[i - 1]) {
				max = Math.max(max, count);
				count = 1;
			} else {
				count++;
			}
		}
		max = Math.max(max, count);
		return max;
	}

	public int findNumberOfLIS(int[] nums) {
		int[] dp = new int[nums.length];
		int[] maxes = new int[nums.length];
		int maxHistory = 0;
		for (int i = 0; i < dp.length; i++) {
			dp[i] = 1;
			for (int j = 0; j < i; j++) {
				if (nums[i] > nums[j]) {// 增序
					if (maxes[i] < maxes[j] + 1) {
						maxes[i] = maxes[j] + 1;
						dp[i] = dp[j];
					} else if (maxes[i] == maxes[j] + 1) {
						dp[i] += dp[j];
					}
				}
			}
			maxHistory = Math.max(maxes[i], maxHistory);
		}
		// System.out.println(maxHistory);
		int max = 0;
		for (int i = 0; i < dp.length; i++) {
			if (maxHistory == maxes[i]) {
				max += dp[i];
			}
		}
		return max;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] nums = { 2, 2, 2, 2, 2 };
		System.out.println(new NumberofLongestIncreasingSubsequence().findNumberOfLIS(nums));
	}

}
